package org.example.code.test2024.ten_mouth;

import java.util.Arrays;

public class test1028 {
    public static void main(String[] args) {
        test1028 test = new test1028();
        int[] num = {8,9,2,7,1,3};
        int[] ints = test.sortQuick(num,0,5);
        System.out.println(Arrays.toString(ints));
    }

    public void count(int[] nums){
        int l=0,r=nums.length-1;
        int[] temp = new int[nums.length];
        System.out.println(countOne(l,r,nums,temp));
    }

    private int countOne(int l, int r, int[] nums, int[] temp) {
        if(l>=r){
            return 0;
        }
        int mid = (l+r)/2;
        int count = countOne(l,mid,nums,temp);
        count = count + countOne(mid+1,r,nums,temp);
        count = count + countTwo(l,r,mid,nums,temp);
        return count;
    }

    private int countTwo(int l, int r, int mid, int[] nums, int[] temp) {
        int i=l,j=mid+1;
        int k=0,count=0;
        while(i<=mid&&j<=r){
            if(nums[i]<nums[j]){
                temp[k++]=nums[i++];
            }else{
                temp[k++]=nums[j++];
                count = count + (mid-i+1);
            }
        }
        while(i<=mid){
            temp[k++]=nums[i++];
        }
        while(j<=r){
            temp[k++]=nums[j++];
        }
        for(i=l;i<=r;i++){
            nums[i]=temp[i];
        }
        return count;
    }

    public void step(int[] nums){
        int move = 0,n=nums.length-1;
        while(!isBalence(nums)){
            for(int i=0;i<n;i++){
                if(nums[i]>nums[i+1]){
                    nums[i]--;
                    nums[i+1]++;
                    move++;
                }else{
                    nums[i]++;
                    nums[i+1]--;
                    move++;
                }
                System.out.println(Arrays.toString(nums));
            }
        }
        System.out.println(move);
    }

    private boolean isBalence(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        int n = sum% nums.length,first = nums[0];
        for(int i=0;i< nums.length;i++){
            if(nums[i]!=first&&Math.abs(first-nums[i])>n){
                return false;
            }
        }
        return true;
    }

    public int[] sortQuick(int[] nums,int l,int r) {
        int start =l;
        int end = r;
        int t = nums[start];
        while(start<end){
            while(nums[start]<t&&start<end){
                start++;
            }
            while(nums[end]>t&&start<end){
                end--;
            }
            if(nums[start]==nums[end]&&start!=end){
                start++;
            }else{
                int temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
            }
        }
        if(start-1>l){
            nums = sortQuick(nums,l,start-1);
        }
        if(end+1<r){
            nums = sortQuick(nums,end+1,r);
        }
        return nums;
    }
}
